package com.heima.algorithm.sort;

import java.util.concurrent.ThreadLocalRandom;

/**
 * <strong>双边循环快速排序（Hoare霍尔分区方案）</strong>
 * <ul>
 *     霍尔分区方案：
 *     <li>选择最左元素作为基准元素</li>
 *     <li>指针le负责找到比基准元素小或等的元素</li>
 *     <li>指针gt负责找到比基准元素大的元素</li>
 *     <li>指针le从数组最右元素往左走，指针gt从数组最左元素往右走</li>
 *     <li>当le == gt则退出循环，并将基准元素放在相遇位置处</li>
 * </ul>
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/1 11:28
 */
public class QuickSortHoare {
    //（1）基于比较的排序算法
    //（2）最好情况：O(NlogN)，最坏情况：O(N^2)，平均情况：O(NlogN)，空间复杂度：O(logN)，稳定：否，思想：分而治之
    //（3）快排可能存在最坏情况，需要把枢轴值选取得尽量随机化来缓解最坏情况下的时间复杂度
    //（4）最好情况就是分区每次都很均匀，递归深度就是logN，每次分区操作需要N，所以最好O(NlogN)，最坏情况就是分区极不平衡，一边0一边剩余所有，这种递归深度就是N

    /**
     * 快速排序
     *
     * @param arr 待排序数组
     */
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序递归实现
     *
     * @param arr   待排序数组
     * @param begin 待排序范围的起始索引（包含）
     * @param end   待排序范围的结束索引（包含）
     */
    private static void quickSort(int[] arr, int begin, int end) {
        // 递归结束条件：当前范围数组内只有一个元素，这里用大于等于，想象两个元素分区后的情况
        if (begin >= end) {
            return;
        }
        // 递的时候将基准点元素放到合适位置并且把比基准点小的元素放基准点元素左边，比基准点大或等的元素放基准点元素右边
        int pivot = partition(arr, begin, end);
        // 再对基准点左边的区域和右边的区域进行快速排序
        quickSort(arr, begin, pivot - 1);
        quickSort(arr, pivot + 1, end);
    }

    /**
     * 霍尔分区思想进行分区操作
     *
     * @param arr   待分区数组
     * @param begin 待分区范围的起始索引（包含）
     * @param end   待分区范围的结束索引（包含）
     * @return 分区好后的基准点元素索引
     */
    private static int partition(int[] arr, int begin, int end) {
        int le = end; // le指针负责找到小于等于基准点的元素
        int gt = begin; // gt指针负责找到大于基准点的元素
        // 随机选择一个元素作为基准点，这样优化的原因是因为当待排序数组是完全倒序的情况下，le指针每走一步都会停下来，gt每次循环都要走到末尾，变成了最坏情况
        int index = ThreadLocalRandom.current().nextInt(end - begin + 1) + begin; // 用随机元素作为基准点，ThreadLocalRandom线程安全
        swap(arr, index, begin); // 将随机元素放到数组最左端
        int pivot = arr[begin]; // 基准点元素
        while (le > gt){ // 当le和gt没有相遇，继续循环，为什么没有等于，因为既找到小于等于又找到大于是不可能的
            while (le > gt && arr[le] > pivot){ // le当前位置的元素大于基准点元素，则继续向左移动le指针寻找小于等于基准点的元素，但是le不能减得小于gt
                le--; // 如果数组全是重复元素，le每次第一个就会停下，导致gt每次都会走到头，导致分区极度不平衡
            }
            while (le > gt && arr[gt] <= pivot){ // gt当前位置的元素小于等于基准点元素，则继续向右移动gt指针寻找大于基准点的元素，但是gt不能大于le
                gt++;
            }
            // 上述两个while循环不能交换顺序，
            swap(arr, le, gt); // 将le和gt位置的元素交换
        }
        swap(arr, le, begin); // 将基准点元素放到合适位置
        return le; // 返回基准点元素索引
    }

    /**
     * 交换两个元素
     *
     * @param arr    数组
     * @param index1 索引1
     * @param index2 索引2
     */
    private static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}
